A. Field of the Invention
The present invention relates generally to routing systems and, more particularly, to systems and methods for routing packets through a network on alternate paths.
B. Description of Related Art
Currently, several types of communication systems exist, including wireless, wired, optical, and hybrid wireless/wired/optical communication systems. Often times, these systems include a network of interconnected nodes. Each node connects to neighboring nodes via a link. The link may be a wireless, wired, or optical communication channel, depending on the type of system in which it is used.
Communication through these systems involves transmitting a packet of data from a source node to a destination node. Often times, a path from the source node to the destination node is predetermined so that each node can determine how to route a received packet. Sometimes, however, the path is established on-the-fly based on cost factors, such as shortest path, signal strength, connection speed, etc. In these cases, the nodes route a packet to minimize the cost of sending the packet from the source node to the destination node.
If a packet transmitted by a node is not successfully received by the next node in one of these systems, the transmission will fail. The source node usually learns of the transmission failure after a timer expires (i.e., after a timeout). In this case, the source node must try to resend the packet, possibly on a different path.
As a result, a need exists to improve the transmission of packets through a network by using alternate paths to minimize the effects of transmission failures between nodes.
Systems and methods consistent with the present invention address this need by determining, at each node, the next best path on which to transmit a packet when transmission on a first path fails.
In accordance with the purpose of the invention as embodied and broadly described herein, a network for routing packets includes multiple nodes. A first node has a direct link to a second node. The first node receives a packet and identifies a primary next hop to which to transmit the packet. The primary next hop identifies at least the second node. The first node transmits the packet to the second node, determines whether the transmission was successful, and identifies at least a third node when the transmission to the second node was unsuccessful.
The first node identifies the third node by: finding a node in the network that has a direct link to both the first and second nodes; identifying at least one alternate next hop, assuming that the link between the first and second nodes is unavailable, determining the cost associated with each of the alternate next hops, and selecting one of the alternate next hops based on the determined cost; or retrieving a predetermined alternate next hop from a forwarding table stored by the first node. The first node then transmits the packet to the third node for forwarding to the second node.
In another implementation consistent with the present invention, a method prevents lost or looping packets in a network. The method includes receiving a packet at a first node; transmitting the packet to a second node on a primary path; determining whether the transmission was successful; identifying a third node on an alternate path when the transmission to the second node was unsuccessful; adding a header to the packet, the header identifying at least an address of the second node; transmitting the packet to the third node; analyzing the packet by the third node to identify the address of the second node from the header; sending the packet to the second node using the identified address; receiving the packet at the second node; and clearing the header by the second node.